package LeetCode_102;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @author : niu niu
 * @version : 1.0.0
 * @date : 2022/10/30 12:04
 * 102. 二叉树的层序遍历
 */
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }

        // 定义两个队列
        Queue<TreeNode> nodeQueue = new LinkedList<>();
        Queue<Integer> levelQueue = new LinkedList<>();

        // 根结点记为第 0 层
        // 把根结点和它对应的层数放入队列中
        nodeQueue.offer(root);
        levelQueue.offer(0);

        // 定义一个记录上次遍历元素的层数，为了找到每一层的第一个元素
        // 一开始使用 != 0（根的层数） 的值就行
        int prevLevel = -1;

        while (!nodeQueue.isEmpty()) {
            TreeNode node = nodeQueue.poll();
            int level = levelQueue.poll();

            if (prevLevel != level) {
                // 新的一层开始了
                ans.add(new ArrayList<>());  // 元素类型是 Integer
            }

            // 更新 prevLevel，始终让 prevLevel 记录上一层遍历的层数
            prevLevel = level;

            // 每个结点的 level 就刚好对应 ans 中的下标，根据这个下标，就可以获取到对应的 List<Integer>，这层的 List
            // 这样就保证了下标不会越界，也就是对应层数的 List<Integer> 一定在 ans 中了
            List<Integer> levelList = ans.get(level);
            // 将元素放入对应的 levelList 中（尾插，保证顺序不变）
            levelList.add(node.val);

            // 层序遍历的模板代码
            if (node.left != null) {
                nodeQueue.offer(node.left);
                levelQueue.offer(level + 1);
            }

            if (node.right != null) {
                nodeQueue.offer(node.right);
                levelQueue.offer(level + 1);
            }
        }

        return ans;
    }
}